{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python_defaultSpec_1597917229322",
   "display_name": "Python 3.8.3 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 扫雷游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "让我们一起来玩扫雷游戏！\n",
    "\n",
    "给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。\n",
    "\n",
    "现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板：\n",
    "\n",
    "1. 如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。\n",
    "2. 如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的未挖出方块都应该被递归地揭露。\n",
    "3. 如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。\n",
    "\n",
    "4. 如果在此次点击中，若无更多方块可被揭露，则返回面板。\n",
    " \n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/minesweeper\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "思路，自己没想出来\n",
    "\n",
    "还是看的题解\n",
    "\n",
    "主要没想到可以在一次递归里面先看看周围有没有雷，还想着只循环一次8个方向，就可以得到结果。还是太年轻了。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "\n",
    "        def in_area(x, y):\n",
    "            return x >= 0 and y >= 0 and x < m and y < n\n",
    "\n",
    "        visited = []\n",
    "        dir = ((-1, -1), (-1, 0), (-1, +1), (0, -1), (0, +1), (1, -1), (1, 0), (1, 1))\n",
    "        # 结束\n",
    "        if board[click[0]][click[1]] == \"M\":\n",
    "            board[click[0]][click[1]] = \"X\"\n",
    "            return board\n",
    "\n",
    "        def helper(x, y):\n",
    "            cnt = 0\n",
    "            for x_, y_ in dir:\n",
    "                tx, ty = x+x_,y+y_\n",
    "                if not in_area(tx, ty):\n",
    "                    continue\n",
    "\n",
    "                if board[tx][ty] == \"M\":\n",
    "                    cnt += 1\n",
    "            \n",
    "            if cnt > 0:\n",
    "                board[x][y] = str(cnt)\n",
    "            else:\n",
    "                board[x][y] = \"B\"\n",
    "                for x_, y_ in dir:\n",
    "                    tx, ty = x+x_, y+y_\n",
    "                    if not in_area(tx, ty) or board[tx][ty] != \"E\":\n",
    "                        continue\n",
    "                    helper(tx, ty)\n",
    "        helper(*click)\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[['B', '1', 'E', '1', 'B'],\n ['B', '1', 'M', '1', 'B'],\n ['B', '1', '1', '1', 'B'],\n ['B', 'B', 'B', 'B', 'B']]"
     },
     "metadata": {},
     "execution_count": 28
    }
   ],
   "source": [
    "board= [['E', 'E', 'E', 'E', 'E'],\n",
    " ['E', 'E', 'M', 'E', 'E'],\n",
    " ['E', 'E', 'E', 'E', 'E'],\n",
    " ['E', 'E', 'E', 'E', 'E' ]]\n",
    "click = [3, 0]\n",
    "\n",
    "Solution().updateBoard(board, click)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "[['B', '1', 'E', '1', 'B'], ['B', '1', 'M', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']]\n"
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "[['B', '1', 'E', '1', 'B'],\n ['B', '1', 'M', '1', 'B'],\n ['B', '1', '1', '1', 'B'],\n ['B', 'B', 'B', 'B', 'B']]"
     },
     "metadata": {},
     "execution_count": 33
    }
   ],
   "source": [
    "board = [[\"B\",\"1\",\"E\",\"1\",\"B\"],[\"B\",\"1\",\"M\",\"1\",\"B\"],[\"B\",\"1\",\"1\",\"1\",\"B\"],[\"B\",\"B\",\"B\",\"B\",\"B\"]]\n",
    "click = [1,2]\n",
    "Solution().updateBoard(board, click)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}